package com.lcm.algorithm.datatest.dp.knapsack.Knapsack01;

/**
 * @description:
 * @author: lcm
 * @create: 2020-04-25 10:02
 **/

public class CanPartition {

    public static void main(String[] args){
        System.out.println(canPartition(new int[]{1, 5, 11, 5}));
    }

    /**
     * 一个数组要分成两个想到的数组，比如1, 5, 11, 5，那么每个子集的和都应该为11，
     * 且只需要找到一个和为11的子集，那么另外一个子集必然也是11.
     * 所以问题被转换成从数组中找一个和为11的子集。
     * 如果能找到和为11的子集，只有两种可能：
     * 1.不包含第i个数
     * 2.包含第i个数
     * f(i,s)=f(i-1,s)||f(i-1,s-vi)
     * f(s)=f(s)||f(s-vi)
     */
    public static boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum=sum+nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        sum=sum/2;

        boolean[] dp=new boolean[sum+1];
        dp[0]=true;
        for(int i=1;i<nums.length;i++){
            for(int j=sum;j>=nums[i];j--){
                dp[j]=dp[j]||dp[j-nums[i]];
            }
        }

        return dp[sum];
    }
}
